﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace Job.Core.Collections
{
    /// <summary>
    /// 基于二分查询算法的范型序列，序列中的元素均必需是唯一的(可考虑用于静态缓存)。
    /// </summary>
    /// <typeparam name="T">需实现 IDichotomyNode 接口。</typeparam>
    [Serializable]
    public class DichotomyList<T> : IEnumerable<T> where T : IDichotomyNode
    {
        #region Properties

        private IList<T> list;

        /// <summary>
        /// 获取序列 
        /// </summary>
        public IList<T> List
        {
            get { return list; }
        }

        /// <summary>
        /// 获取序列包含元素数目。
        /// </summary>
        public int Count
        {
            get { return list.Count; }
        }

        /// <summary>
        /// 获取用于线程同步的对象。
        /// </summary>
        public virtual object SyncRoot { get; protected set; }

        /// <summary>
        /// 指示当前序列是否为线程安全的。
        /// </summary>
        public virtual bool IsSynchronized { get; protected set; }

        #endregion

        #region Constructor

        /// <summary>
        /// 初始化 DichotomyList 类的新实例。
        /// </summary>
        public DichotomyList()
        {
            list = new List<T>();
        }

        /// <summary>
        /// 使用已有序列初始化 DichotomyList 类的新实例。
        /// </summary>
        /// <param name="list">初始化序列。</param>
        public DichotomyList(IList<T> list)
        {
            if (list == null)
                this.list = new List<T>();
            else
                this.list = list;

            if (!Initialize())
                throw new ArgumentException("初始化失败，序列中包含相同 Id 的元素。");
        }

        #endregion

        #region Static

        /// <summary>
        /// 返回 DichotomyList 实例的同步包装。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">需包装的序列。</param>
        /// <returns>线程安全的 DichotomyList。</returns>
        public static DichotomyList<T> Synchronized(DichotomyList<T> list)
        {
            if (list == null)
                throw new ArgumentNullException("list");

            //已经是同步list，直接返回。
            if (list.IsSynchronized == true && list is SyncDichotomyList)
                return list;

            return new SyncDichotomyList(list);
        }

        #endregion

        #region Methods

        /// <summary>
        /// 向序列中添加一个元素。
        /// </summary>
        /// <param name="item">要添加的元素。</param>
        public virtual void Add(T item)
        {
            if (item == null)
                throw new ArgumentNullException("item");

            T temp;
            if (FindByDichotomy(item.KeyId, out temp) != -1)
                throw new ArgumentException("指定的元素已存在。");

            list.Add(item);
            Initialize();
        }

        /// <summary>
        /// 切换/变更序列中的一个元素，用于更新已变更的元素。
        /// </summary>
        /// <param name="item">要变更的元素。</param>
        public virtual void Toggle(T item)
        {
            if (item == null)
                throw new ArgumentNullException("item");

            T temp;

            int index = FindByDichotomy(item.KeyId, out temp);
            if (index != -1) list[index] = item;
        }

        /// <summary>
        /// 移除指定 Keyid 的元素。
        /// </summary>
        /// <param name="id">Keyid。</param>
        public virtual void Remove(IComparable id)
        {
            if (id == null)
                throw new ArgumentNullException("id");

            T temp;
            if (FindByDichotomy(id, out temp) != -1)
                list.Remove(temp);
        }

        /// <summary>
        /// 清除序列中的所有元素。
        /// </summary>
        public virtual void Clear()
        {
            list.Clear();
        }

        /// <summary>
        /// 获取指定 id 的元素，当不存在抛出异常。
        /// </summary>
        /// <param name="id">id。</param>
        /// <returns>指定 id 的元素。</returns>
        public virtual T Get(IComparable id)
        {
            if (id == null)
                throw new ArgumentNullException("id");

            T temp;
            if (FindByDichotomy(id, out temp) != -1)
                return temp;

            throw new InvalidOperationException("序列未包含指定的元素。");
        }

        /// <summary>
        /// 获取指定 id 的元素，当不存时返回类型默认值。
        /// </summary>
        /// <param name="id">id。</param>
        /// <returns>指定 id 的元素，如果不存在则返回类型默认值。</returns>
        public virtual T GetOrDefault(IComparable id)
        {
            if (id == null)
                throw new ArgumentNullException("id");

            T temp;

            if (FindByDichotomy(id, out temp) != -1)
                return temp;

            return default(T);

        }

        /// <summary>
        /// 检查指定 id 的元素是否已存在于序列中。
        /// </summary>
        /// <param name="id">id。</param>
        /// <returns>存在返回 true，否则返回 false。</returns>
        public virtual bool Exists(IComparable id)
        {
            if (id == null)
                throw new ArgumentNullException("id");

            T temp;
            return FindByDichotomy(id, out temp) != -1;
        }

        /// <summary>
        /// 使用二分法对列表进行初始化排序。
        /// </summary>
        /// <returns>成功返回 true，否则返回 false。</returns>
        private bool Initialize()
        {
            T tmp;
            int left, right;
            int middle, j;
            for (int i = 1; i < list.Count; i++)
            {
                left = 0;
                right = i - 1;
                tmp = list[i];
                while (right >= left)
                {
                    middle = (left + right) / 2;
                    int val = tmp.KeyId.CompareTo(list[middle].KeyId);
                    if (val < 0)
                        right = middle - 1;
                    else if (val > 0)
                        left = middle + 1;
                    else
                        return false;
                }

                for (j = i - 1; j >= left; j--)
                    list[j + 1] = list[j];

                list[left] = tmp;
            }

            return true;
        }

        /// <summary>
        /// 用二分法查找指定 id 的元素所在索引值，未存在指定 id 的元素时返回 -1。
        /// </summary>
        /// <param name="id">id。</param>
        /// <param name="output">output 元素实例，如果未找到匹配 id 的实例，则填充类型的默认值。</param>
        /// <returns>所在序列中的索引值，不存在则返回 -1。</returns>
        private int FindByDichotomy(IComparable id, out T output)
        {
            output = default(T);
            int low, high, mid;
            low = 0;
            high = list.Count - 1;

            while (low <= high)
            {
                mid = (low + high) / 2;
                if (id.CompareTo(list[mid].KeyId) == 0)
                {
                    output = list[mid];
                    return mid;
                }
                if (id.CompareTo(list[mid].KeyId) < 0) high = mid - 1;
                else low = mid + 1;
            }

            return -1;
        }

        #endregion

        #region IEnumerable<T> 成员

        public IEnumerator<T> GetEnumerator()
        {
            return list.GetEnumerator();
        }

        #endregion

        #region IEnumerable 成员

        IEnumerator IEnumerable.GetEnumerator()
        {
            return list.GetEnumerator();
        }

        #endregion

        #region SyncDichotomyList

        /// <summary>
        /// 同步包装的 DichotomyList。
        /// </summary>
        [Serializable]
        class SyncDichotomyList : DichotomyList<T>
        {
            internal SyncDichotomyList(DichotomyList<T> list)
            {
                this.list = list.list;
                IsSynchronized = true;
                SyncRoot = new object();
            }

            #region Overrides

            public override void Add(T item)
            {
                lock (SyncRoot)
                {
                    base.Add(item);
                }
            }

            public override void Remove(IComparable id)
            {
                lock (SyncRoot)
                {
                    base.Remove(id);
                }
            }

            public override void Clear()
            {
                lock (SyncRoot)
                {
                    base.Clear();
                }
            }

            #endregion
        }

        #endregion

    }
}